Transparent speculative coordination

In distributed computing, two actors want to act in unison. The following sketch outlines a protocol for synchronisation with honest actors but unreliable communication. This is a relaxation of the Byzantine Fault Tolerance problem, as consistency does not have to be reached within a specifc timeframe, and actors can act on their own. The only important thing is that once someone commits to act, everyone will eventually follow.

At its core, it uses speculative execution, and both actors can see the latest state of each other in unreliable intervals.

Syncing state

Whenever an actor sees another actor's snapshot with a more recent state than its own, it adopts that state.

Proposing an action

Precondition: The proposing actor sees every other actor's current snapshot and they are all in the same state S(t), with no staged actions.

• t: A and B start and see each other in S(t). A stages move. B stays idle.
• t+1: A sends B its snapshot ("t staged move").
• t+2: If B sees the staged move, it follows and applies it to S(t+2).
• t+3: If A witnesses B, it also goes to S(t+2). Else, it rolls back to S(t) and aborts.
• t+…: If B does not witness A applying S(t+2), it still stays in that state, and as soon as A witnesses B's newer (t+2 > t) state, it syncs into S(t+2).

Breaking ties

If multiple actions are staged during the same round, the action which is ordered highest with respect to some ordering is taken on by all actors who witness it. Idling is always the lowest possible action. An actor can only switch to actions other actors propose, but not overwrite its own staged action on its own accord. This means for n actors, every round, at most n distinct actions can be proposed, and no actor can propose more than once per round.

Trustlessness

The trust assumption of the protocol can probably be removed if this protocol is executed in a nested fashion: the latest agreed-upon action is rolled back if a proof of misbehaviour is supplied, but the state before that is immutable. If two actors commit to different states, both states are discarded and the last round is repeated. If someone commits to a future state, it is not adopted by honest participants. As the next round only starts locally after witnessing everyone else to have finished the last round in unison, and with one actor being censored, the whole protocol stalls until reliable communications are restored. All honest nodes will always have the exact same last immutable committed state, though they may differ in their last committed state in the presence of adversarial actors; But since that is only a speculative commitment, they are still fully synchronised.

Usability improvements

There are two important improvements left to make this protocol usable:

• The ability to stage moves for the next rounds (stacking two or more staged moves) so that the protocol is pipelined and the best-case throughput is one or more moves per round.
• The ability to do "no-op" moves that make a state immutable even in the absence of real actions.